#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void backtrack(vector<int> &data, vector<int> &tmp, int l, int r, int &res)
{
    if (l == r)
    {
        return;
    }
    int mid = (l + r) / 2;
    backtrack(data, tmp, l, mid, res);
    backtrack(data, tmp, mid + 1, r, res);
    arraySort(data, tmp, l, mid, r, res);
}

void arraySort(vector<int> &data, vector<int> &tmp, int l, int mid, int r, int &res)
{
    int t = l;
    int i = l;
    int j = mid + 1;
    while (j <= r && i <= mid)
    {
        if (data[i] <= data[j])
        {
            tmp[t] = data[i];
            t++;
            i++;
        }
        else
        {
            tmp[t] = data[j];
            t++;
            j++;
            res += mid + 1 - i; //关键代码
            res %= 1000000007;
        }
    }
    while (j <= r)
    {
        tmp[t] = data[j];
        t++;
        j++;
    }
    while (i <= mid)
    {
        tmp[t] = data[i];
        t++;
        i++;
    }
    for (int t = l; t <= r; t++)
    {
        data[t] = tmp[t];
    }
}

//数组中的逆序对，归并排序，类似leetcode-493.翻转对
int InversePairs(vector<int> data)
{
    int res = 0;
    int len = data.size();
    vector<int> tmp(len, 0);
    backtrack(data, tmp, 0, len - 1, res);
    return res;
}

void test()
{
}

int main()
{
    test();
    return 0;
}